#include<iostream>
#include<queue>
#include<string>
#include<map>
#include<cfloat>
#include<algorithm>
#define ll long long
using namespace std;
struct node{
    int x;
    double jl;
    bool operator<(const node & y)const{
        return jl>y.jl;
    }
};
int n,m;
double e;
int bj[5005];
double jl[5005];
ll count1[5005];
priority_queue<node>q;
vector<node>v[5005];
vector<node>map1[5005];
vector<int>bjb[5005];
ll ans;
double ans1[2000000];
struct node1{
    int x;
    double jl1;
    double jl11;
    node1(double c,int b){
        jl11=c;
        jl1=c+jl[b];
        x=b;
    }
    bool operator<(const node1 & y)const{
        return jl1>y.jl1;
    }
};
priority_queue<node1>q1;
void dfs(int x,double sum){
    if(x==n){
        ans++;
        ans1[ans]=sum;
    }
    if(jl[x]+sum>e)return;
    for(int i=0;i<v[x].size();i++){
        if(!bjb[x][i]){
            if((sum+v[x][i].jl)<=e){
                bjb[x][i]=1;
                dfs(v[x][i].x,sum+v[x][i].jl);
                bjb[x][i]=0;
            }
        }
    }
}
 double minn=DBL_MAX;
 int ans2=0;
void dfs1(int g,double sum,int now){
    if(g>ans2){
        ans2=g;
    }
    if(minn+sum>e)return;
    for(int i=now;i<=ans;i++){
        if((sum+ans1[i])<=e){
            dfs1(g+1,sum+ans1[i],i+1);
        }
    }
}
int main(){
    cin>>n>>m>>e;
    for(int i=1;i<=m;i++){
        int x,y;
        double e1;
        cin>>x>>y>>e1;
        node n;
        n.x=y;
        n.jl=e1;
        node n1;
        n1.x=x;
        n1.jl=e1;
        v[x].push_back(n);
        bjb[x].push_back(0);
        map1[y].push_back(n1);
    }
    for(int i=1;i<=n;i++)jl[i]=DBL_MAX;
    node zd;
    zd.x=n;
    zd.jl=0;
    bj[zd.x]=0;
    jl[zd.x]=0;
    q.push(zd);
    while(!q.empty()){
        node f=q.top();
        q.pop();
        if(bj[f.x])continue;
         bj[f.x]=1;
        for(int i=0;i<map1[f.x].size();i++){
            if(!bj[map1[f.x][i].x]){
                node nn;
                jl[map1[f.x][i].x]=min(jl[map1[f.x][i].x],jl[f.x]+map1[f.x][i].jl);
                nn.x=map1[f.x][i].x;
                nn.jl=jl[map1[f.x][i].x];
                q.push(nn);
            }
        }
    }
    q1.push(node1(0,1));
     int limit = int(e/ jl[1]) + 1;
    while(!q1.empty()){
        node1 f=q1.top();
        q1.pop();
        if(f.x==n){
            ans++;
            ans1[ans]=f.jl11;
            continue;
        }
        if(ans>limit)break;
        // if(f.jl1>e)break;
         count1[f.x]++;
         if(count1[f.x]>limit)break;
        for(int i=0;i<v[f.x].size();i++){
            if(f.jl11+v[f.x][i].jl<=e){
               
                q1.push(node1(f.jl11+v[f.x][i].jl,v[f.x][i].x));
            }
        }
    }
    sort(ans1+1,ans1+1+ans);
    int fa=0;
    double sum=0;
    for(int i=1;i<=ans;i++){
        if(sum+ans1[i]<=e){
            sum+=ans1[i];
            fa++;
        }
        else break;
    }
    cout<<fa;
    return 0;
}